#!/usr/bin/perl 
#
# autosort.pl - modified by AF 2009-08-25
#
# This program sorts submissions to reviewers based on keyword matches.
#
# The underlying algorithm is based on the Gale-Shapley solution to
# the Stable Marriage Problem.  See Gusfield & Irving, The Stable
# Marriage Problem: Structure and Algorithms, as well as:
#    http://en.wikipedia.org/wiki/Stable_marriage_problem
#
# The algorithm "optimally" assigns reviewers to submissions based on
# preference lists -- each reviewer an ordered preference list of
# submissions, and each submission has an ordered list of preferences
# for the reviewers. (In this program, the preferences are simply
# rankings based on a scoring of how well the reviewer matches the
# submissions, based on keywords that both have chosen. More on this
# score momentarily.) The algorithm provides a simple guarantee: that
# after the assignments are made there is no "unstable pair". An
# unstable pair is as follows: a reviewer R prefers a submission S
# (not assigned to R) over one of the submissions that is currently
# assigned to R; and S prefers R to one of the reviewers currently
# assigned to S.
#
# Preference lists are formed by sorting accoring to a score that 
# says how well each reviewer matches each submission, based on the
# keywords attached to each of them. The higher the score the better
# the match. If the keywords picked by a reviewer and a submission
# matched exactly, then they would get a score of 1. However, that
# never happens in practice and typically scores are less than 0.5.
# In addition, matches where the reviewer is said to be "expert" 
# count more than where the reviewer is "knowledgeable" and the 
# *order* of the keywords picked by the submission matters too
# (earlier keywords in the list count more). Finally, if a reviewer
# has just a few keywords then every match counts for more than if
# he has many keywords. This is all pretty complicated. See the last
# subroutine "ScoreSubRev()" in this file for details.
#
# This program has been used for revier assignments by several
# program chairs for ACM Siggraph in 2007-2009, including: sketches
# and posters 2007, initial sort for technical papers 2008, general
# submission and late breaking programs 2008 and 2009 and art papers
# 2009. Typically, this program provides an initial sort that is 
# subsequently tweaked by hand by the program chair to fill in gaps,
# handle late reviewer additions, weak assignments, etc.
#
# This program was written by Adam Finkelstein <af@princeton.edu> in
# July 2007.  It was adapted from an earlier prototype built in April
# 2007 by Adam Finkelstein and Marc Alexa <marc.alexa@tu-berlin.de>.
#
#     This program is free software: you can redistribute it and/or modify
#     it under the terms of the GNU General Public License as published by
#     the Free Software Foundation, either version 3 of the License, or
#     (at your option) any later version.
#
#     This program is distributed in the hope that it will be useful,
#     but WITHOUT ANY WARRANTY; without even the implied warranty of
#     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#     GNU General Public License for more details.
#
#     You should have received a copy of the GNU General Public License
#     along with this program.  If not, see <http://www.gnu.org/licenses/>.
#

######################################################################
# SECTION: Initialization
######################################################################

# optional command line args specify reviewer and submission capacities
$arg0 = int($ARGV[0]);
$arg1 = int($ARGV[1]);
$arg2 = int($ARGV[2]);
$arg3 = int($ARGV[3]);
$arg4 = int($ARGV[4]);

# a note on the non-obvious variable tmpFilePrefix - 
#
# this is a kludge to get around a file permissions problem.
# it allows the program to be run *by the web server* (not me)
# and write all files in a local sub directory called "run" to 
# which it has permissions. on the other hand, when i run the 
# program by command line, all the files are written in a 
# different directory ("urun").
#

$maxAssignPerRev   = ($arg0 > 0) ? $arg0 : 15; # defaults
$maxAssignPerSub   = ($arg1 > 0) ? $arg1 : 2;
$revRequestValue   = ($arg2 > 0) ? $arg2 : 1000.0;
$tmpFilePrefix     = ($arg3 > 0) ? "urun/" : "run/";
$ignoreExtraScores = ($arg4 > 0);

$startDate = `date`;
$bigReport = 0;
$writePrefs = 1;
$writeLog = 1;
$progress = 1;			# says whether to print progress on stdout

print "reading input files ...\n" if ($progress);

if ($writeLog)
{
    $fname = $tmpFilePrefix."log.txt";
    open LOG, ">$fname" or LogDie("cannot open log");
    print LOG "started $startDate";
}

# remove old preferences files if they exist and make new directory
if (!(-e $tmpFilePrefix))
{
    mkdir $tmpFilePrefix or LogDie("cannot make directory $tmpFilePrefix");
}
@args = ("rm", "-rf", $tmpFilePrefix."prefs");
system(@args);
mkdir $tmpFilePrefix."prefs";

srand(0);                       # always generate same list of random numbers

######################################################################
# SECTION: Read input files
######################################################################

##### REVIEWER CAPS #####

$file = $tmpFilePrefix."chair-reviewer-caps.txt";
if (-e $file)
{
    open CAPS, "$file" or LogDie("cannot open $file");
    while (<CAPS>)
    {
	next if /^#/;		# discard comments

	chomp; 
	@words = split;

	$rev = int($words[0]);
	$cap = int($words[1]);
	
	$revCap[$rev] = $cap;

	# print "rev $rev has cap $cap\n";
    }
}
else
{
    print LOG "No caps file found '$tmpFilePrefix'\n";
}
close REQ;

##### REVIEWER REQUESTS #####

open REQ, "map-request.txt" or LogDie("cannot open map-request.txt");
while (<REQ>)
{
    next if /^#/;		# discard comments

    chomp; 
    @words = split;

    $sub = int($words[0]);
    $rev = int($words[1]);

    $requests[$rev][$sub] = 1;
    $numRequests[$rev]++;
}
close REQ;

##### CHAIR REVIEWER REQUESTS #####

$chairReq = $tmpFilePrefix."chair-request.txt";
open REQ, $chairReq or LogDie("cannot open chair-request.txt");
while (<REQ>)
{
    next if /^#/;		# discard comments

    chomp; 
    @words = split;

    $sub = int($words[0]);
    $rev = int($words[1]);

    $requests[$rev][$sub] = 1;
    $numRequests[$rev]++;
}
close REQ;


##### CHAIR AFFINITY ####

$file = $tmpFilePrefix."chair-affinity.txt";
if (-e $file)
{
    open AFF, "$file" or LogDie("cannot open $fname");
    while (<AFF>)
    {
	next if /^#/;		# discard comments

	chomp; 
	@words = split;

	$rev   = int($words[0]);
	$sub   = int($words[1]);
	$score = $words[2];

	$affinity[$rev][$sub] = $score;
	## print "read affinity $score for rev $rev and sub\n";
    }
    close AFF;
}

##### REVIEWER CONFLICTS #####

open CON, "map-conflict.txt" or LogDie("cannot open map-conflict.txt");
while (<CON>)
{
    next if /^#/;		# discard comments

    chomp; 
    @words = split;

    $rev = int($words[0]);
    $sub = int($words[1]);

    $conflicts[$rev][$sub] = 1;
}
close CON;

##### CHAIR SPECIFIED CONFLICTS ######
$chairCon = $tmpFilePrefix."chair-conflict.txt";
open CON, $chairCon or LogDie("cannot open chair-conflict.txt");
while (<CON>)
{
    next if /^#/;		# discard comments

    chomp; 
    @words = split;

    $sub = int($words[0]);
    $rev = int($words[1]);

    $conflicts[$rev][$sub] = 1;
}
close CON;

##### REVIEWER TOPICS #####

# if the chair has added reviewer topics, cat that to the end of the file
$revTop      = "map-reviewer-topics.txt";
$chairRevTop = $tmpFilePrefix."chair-reviewer-topics.txt";
$infile      =  (-e $chairRevTop) ? "cat $revTop $chairRevTop |" : $revTop;
open REV, "$infile" or LogDie("cannot open file: $infile");

$maxRev = 0;

while (<REV>)
{
    next if /^#/;		# discard comments

    chomp;
    ($rev, $top, $expertise) = split;

    # expertise should be either 1 (expert) or 2 (knowledgeable).
    # this translates to weights, respectively, of 1.0 or 0.5
    $weight = 1.0 / $expertise;

    # if the weight for this reviewer and topic had already been set,
    # subsequent assignments (such as those expressed by the chair)
    # will take precedence. note that we have to adjust normalization
    # to only account for the last assignment.
    if ($revTopicWeight[$rev][$top] > 0.0)
    {
	$revNormal[$rev] -= $revTopicWeight[$rev][$top];
    }
    $revTopicWeight[$rev][$top] = $weight;

    # will normalize reviewers to all get equal sum of topic weights
    $revNormal[$rev] += $weight;

    $rev = int($rev);
    if ($maxRev < $rev)
    {
	$maxRev = $rev;		# remember highest reviewer number
    }
}
close REV;


##### SUBMISSION NAMES #####
#
# This info is not strictly necessary, except for error checking and reporting

$infile = "map-submissions.txt";
open SUB, "$infile" or LogDie("cannot open file: $infile");

$maxSub = 0;

while (<SUB>)
{
    next if /^#/;		# discard comments

    # parse out submission ID and keywords for that submission
    chomp; 
    @words = split;
    $sub   = int($words[0]);
    $name  = $words[1];
    $subNames[$sub] = $name;

    if ($maxSub < $sub)
    {
	$maxSub = $sub;		# remember highest numbered sub
    }
}
close SUB;

##### SUBMISSION TOPICS #####

# if the chair has added submission topics, cat that to the end of the file
$subTop      = "map-submission-topics.txt";
$chairSubTop = $tmpFilePrefix."chair-submission-topics.txt";
$infile      =  (-e $chairSubTop) ? "cat $subTop $chairSubTop |" : $subTop;
open SUB, "$infile" or LogDie("cannot open file: $infile");

while (<SUB>)
{
    next if /^#/;		# discard comments

    # parse out submission ID and keywords for that submission
    chomp; 
    @words = split;
    $sub   = int($words[0]);
    $top   = int($words[1]);
    $rank  = int($words[2]);

    if ($maxSub < $sub)
    {
	$maxSub = $sub;		# remember highest numbered sub
    }

    # if the rank for this submission and topic had already been set,
    # subsequent assignments (such as those expressed by the chair)
    # will take precedence.
    if ($subTopicRank[$sub][$top] > 0.0)
    {
	$subTopicRank[$sub][$top] = $rank; 
    }
    else			# otherwise, just add this to the list
    {
	$count = $subTopicCount[$sub];
	$subTopics[$sub][$count]  = $top;
	$subTopicRank[$sub][$top] = $rank; 
	$subTopicCount[$sub]++;
    }

    # remember highest rank for topic attached to this submission
    # (used by weight assignment a few lines down)
    # note: this doesn't work if there was a subsequent assignment
    # as above to the same (sub,topic) pair -- unlikely case, not fatal.
    if ($maxTopicRank[$sub] < $rank)
    {
	$maxTopicRank[$sub] = $rank;
    }

}

######################################################################
# SECTION: Weights & Scores for Keyword Matching -> Preference Lists
######################################################################

# assign weights to the topics attached to each submission.
# first has most weight (1.0) and last has least (0.5)
#   with linear falloff in between.
for ($sub = 1; $sub <= $maxSub; $sub++)
{
    $numWords = $subTopicCount[$sub];
    for ($w = 0; $w < $numWords; $w++)
    {
	$top  = $subTopics[$sub][$w];
	$rank = $subTopicRank[$sub][$top];
	$max  = $maxTopicRank[$sub];

	# alpha is 1.0 for the first entry (lowest rank) and 0.0 for the last
	# (in the case that there is only one word, alpha is 1.0)
	$alpha = ($max == 1.0 || $numWords == 1) ? 1.0 : 
	    ($max - $rank) / ($max - 1.0);

	# weight is 1 for alpha==1 and 0.5 for alpha==0, with lerp
	$weight = 0.5 * $alpha + 0.5;

	$subTopicWeight[$sub][$top] = $weight;
	$subNormal[$sub] += $weight;
    }
}

print "computing scores ...\n" if ($progress);

##### GENERATE SCORES #####

for ($sub = 1; $sub <= $maxSub; $sub++)
{
    $numWords = $subTopicCount[$sub];
    if ($numWords < 1)
    {
	$sname = $subNames[$sub];
	$fname = "submission $sname (# $sub of $maxSub)";
###	LogDie("failure -- submission $fname has no topics");
	LogWarn("warning -- $fname has no topics");
    }

    # loop over reviewers to compare keywords for match
    for ($rev = 1; $rev <= $maxRev; $rev++)
    {
	$score = ScoreSubRev($sub, $rev);
	$affin = $affinity[$rev][$sub];
	if ($affin && !$ignoreExtraScores)
	{
	    $score += $affin;
	    ## print "for rev $rev and sub $sub add $affin to score\n";
	}

        if ($conflicts[$rev][$sub])
	{
            print LOG "conflict: do not add rev $rev to sub $sub list (score was $score)\n";
	    $score = 0.0;
	}
        elsif ($requests[$rev][$sub] && !$ignoreExtraScores)
        {
	    $bump   = $revRequestValue / $numRequests[$rev];
	    $score += $bump;
            print LOG "reviewer $rev requested sub $sub (bumping score by $bump to $score)\n";
        }

	# add epsilon to eliminate ties (makes arbitrary order fair)
	if ($score > 0.0) 
	{
            $score += 1e-9 * rand();
	}
	else # eliminate negative scores (shoudn't really happen)
	{
	    $score = 0.0;
	}

	# remember score for this reviewer and this submission
	$scores[$rev][$sub] = $score;
    }
}

##### REVIEWER PREFERENCE LIST #####

for ($rev = 1; $rev <= $maxRev; $rev++)
{
    if ($writePrefs)
    {
	$fname = sprintf($tmpFilePrefix."prefs/rev-%04d.txt", $rev);
	open PREF, ">$fname" or LogDie("cannot open $fname");
    }

    @list = ();
    for ($sub = 1; $sub <= $maxSub; $sub++)
    {
	$score = $scores[$rev][$sub];

        # NOTE: Policy decision! (Are zero scores acceptible?)
        if ($score == 0.0)	
        {
            print LOG "\t\tscore 0: do not add rev $rev to sub $sub list\n";
        }
        else
        {
	    push @list, {sub=>$sub, score=>$score};
	}
    }

    # sort this list in order of decreasing score
    @list = sort {$b->{score} <=> $a->{score}} @list;

    # keep the list of reviewers in sorted order (but forget the scores now)
    $num = 0;
    print PREF "# preference list for reviewer $rev (rank, sub id, score):\n";
    for (@list)
    {
	$sub = $_->{sub};
	$score = $_->{score};
	$score = sprintf("%5.2f",$score);
	$revPref[$rev][$num] = $sub;
	$num++;
	$revRank[$rev][$sub] = $num;
	print PREF "$num\t$sub\t$score\n";
    }
    $revPrefNum = $num;
    close PREF;
}

##### SUBMISSION PREFERENCE LIST #####

# now need rank lists for submissions (for reporting)

for ($sub = 1; $sub <= $maxSub; $sub++)
{
    if ($writePrefs)
    {
	$fname = sprintf($tmpFilePrefix."prefs/sub-%04d.txt", $sub);
	open PREF, ">$fname" or LogDie("cannot open $fname");
    }

    @list = ();
    for ($rev = 1; $rev <= $maxRev; $rev++)
    {
	$score = $scores[$rev][$sub];
	if ($score > 0.0)
	{
	    push @list, {rev=>$rev, score=>$score};
	    $sc = int($score * 10.0);
	    $scoreHisto[$sc]++;
	    if ($maxScoreHisto < $sc)
	    {
		$maxScoreHisto = $sc;
	    }
	}
    }
    # sort this list in order of decreasing score
    @list = sort {$b->{score} <=> $a->{score}} @list;

    print PREF "# preference list for submission $sub (rank, rev id, score):\n";

    # pull them off the list in order, recording rankings
    $num = 0;
    for (@list)
    {
	$rev   = $_->{rev};
	$score = $_->{score};
	$score = sprintf("%5.2f",$score);
	$num++;
	$subRank[$rev][$sub] = $num;
	print PREF "$num\t$rev\t$score\n";
    }
}

##### ASSIGN EVERYONE FREE ###

for ($rev = 1; $rev <= $maxRev; $rev++)
{
    $revAssignNum[$rev] = 0;
    $nextSub[$rev] = 0;
}

@empty = ();
for ($sub = 1; $sub <= $maxSub; $sub++)
{
    @{$subAssign[$sub]} = @empty;
}

######################################################################
# SECTION: Make the assignments based on preference lists
######################################################################

##### THE FUN PART ######
print "now the fun begins...\n" if ($progress);

# p. 39 of Gusfield and Irving, 
#   The Stable Marriage Problem: Structure and Algorithms
# Hospitals are reviewers and residents are submissions
# (also, 1.6.7 p 54 discusses many-many version)
#
# 0. create preference lists for reviewers 
# 1. assign each submission to be free 
# 2. assign each reviewer to be totally unsubscribed 
# 3. while ( (some reviewer R is undersubscribed)
# 4.         AND (R is not at the end of his list) ) DO
# 5.   BEGIN
# 6.      S := next submission on R's list (advance each time)
# 7.      IF (S is already fully assigned) THEN
# 8.          W := worst match for S so far
# 9.          IF score(S,R) < score(S,W) skip to END
# 10.         S dumps W
# 11.     assign R to S 
# 12.  END

ASSIGN: while (1)
{
  SEEK: for ($rev = 1; $rev <= $maxRev; $rev++)
    {
	$next   = $nextSub[$rev];
        $sub    = $revPref[$rev][$next];
	$revMax = defined($revCap[$rev]) ? $revCap[$rev] : $maxAssignPerRev;   # is there a cap for this rev?
	if (defined($revCap[$ref]))
	{
	    print LOG "Reviewr cap $rev $revCap[$rev]\n";
	}

	if ( ($revAssignNum[$rev] < $revMax)
             && ($sub) )        # make sure we have not run off end of preference list
	{
	    print LOG "found rev $rev with only $revAssignNum[$rev] assignments and next sub $sub\n";
            $nextSub[$rev]++;   # advance the pointer for next time
	    last SEEK;
	}
    }

    if ($rev > $maxRev)         # checked all and did not find candidate proposal; quit proposing
    {
        print LOG "done with assignments - no good ones left\n";
        last ASSIGN;
    }

    $score = $scores[$rev][$sub];

    # note that sub assigments are stored in an array of hashes, in terminology of:
    #   http://www.scit.wlv.ac.uk/~jphb/perl/pod/perldsc.html#arrays%20of%20hashes
    #
    @subAssignments = @{$subAssign[$sub]};
    $subAssignCount = @subAssignments;

    if ($subAssignCount >= $maxAssignPerSub)
    {
	# find worst match among current assignments to $sub
	print LOG "checking current assignments for sub $sub...\n";

        # sort this list in order of increasing score
        @subAssignments = sort {$a->{score} <=> $b->{score}} @subAssignments;

	$worstRev   = $subAssignments[0]->{rev};
	$worstScore = $subAssignments[0]->{score};

	print LOG "compare score $score to worst score for sub $sub: $worstScore (for rev $worstRev)\n";
	if ($score < $worstScore)
	{
	    print LOG "\tno improvement so MOVE ON\n";
	    next ASSIGN;	# go on to try the next one
	}

	# S dumps W: remove W from S's list of assignments
	print LOG "sub $sub dumps worst rev $worstRev\n";
        shift(@subAssignments);                   # pull worst match off list
        @{$subAssign[$sub]} = @subAssignments;    # save the resulting list

        # next: decrement assignment counts
        $revAssignNum[$worstRev]--;
	$subAssignCount--;
	print LOG "\tnow worst rev $worstRev has $assignments assignments:\n\t";
	print LOG "\tnow sub $sub has $subAssignCount assignments:\n\t";
    }

    # assign R to S
    push @{$subAssign[$sub]}, {rev=>$rev, sub=>$sub, score=>$score};
    $subAssignCount++;
    $revAssignNum[$rev]++;

    print LOG "assign rev $rev to sub $sub...\n";
    print LOG "\trev now has $revAssignNum[$rev] assignments\n";
    print LOG "\tsub now has $subAssignCount assignments\n";
}

######################################################################
# SECTION: Report assigments and a bunch of stats on how we did
######################################################################

print "report...\n" if ($progress);

if ($bigReport)
{
    $fname = $tmpFilePrefix."report.txt";
    open REPORT, ">$fname" or LogDie("cannot open report");
    print REPORT "Started $startDate\n";
}

###### WRITE OUT ASSIGNMENTS ######

$fname = $tmpFilePrefix."assignments.txt";
open  ASSIGN, ">$fname" or LogDie("cannot open assignments.txt");
print ASSIGN  "# sub\trev\tscore\ts-rank\tr-rank\n";

# run over submissions writing out info, but also note which are matched
for ($sub = 1; $sub <= $maxSub; $sub++)
{
    @subAssignments = @{$subAssign[$sub]};
    $subAssignCount = @subAssignments;

    $sHisto[$subAssignCount]++;

    print REPORT "Assignments for submission $sub:";
    $ave = 0;
    $aveRank = 0;
    for (@subAssignments)
    {
	$rev   = $_->{rev};
	$score = $_->{score};
	$ave  += $score;
	$srank = $subRank[$rev][$sub];
	$rrank = $revRank[$rev][$sub];
	$score = sprintf("%5.2f",$score);
	$aveRank += $srank;
	print REPORT "\t$rev ($srank,$score)";
	$subRankHisto[$srank]++;

	print ASSIGN "$sub\t$rev\t$score\t$srank\t$rrank\n";
	
        # note matches here
	$matched[$rev][$sub] = 1;

        # save list for validation later
        $subList[$sub][$subListNum[$sub]++] = $rev;
    }
    for ($i = $subAssignCount; $i < $maxAssignPerSub; $i++)
    {
	print REPORT "\t\t";
    }
    $denom = ($subAssignCount ? $subAssignCount : 1);
    $ave     /= $denom;
    $aveRank /= $denom;
    $aveRank = int($aveRank + 0.5);
    $ave     = sprintf("%5.2f",$ave); 
    print REPORT "\tave: ($aveRank,$ave)\n";
}

close(ASSIGN);

print REPORT "========\n";

$minNum = $maxSub;
$maxNum = 0;
$totNum = 0;
$overallA = 0;

for ($rev = 1; $rev <= $maxRev; $rev++)
{
    $num = $revAssignNum[$rev];

    print REPORT "$num assignments for reviewer $rev:\n";
    $ave   = 0;
    $count = 0;
    for ($sub = 1; $sub <= $maxSub; $sub++)
    {
        if ($matched[$rev][$sub])
        {
            $count++;
            $score     = $scores[$rev][$sub];
            $ave      += $score;
            $overallA += $score;
	    $rank      = $revRank[$rev][$sub];
	    $aveRank  += $rank;
	    $score = sprintf("%5.2f",$score);
            print REPORT "\t$sub\t$rank\t$score\n";
	    $rank = int($rank/10.0);
	    $revRankHisto[$rank]++;

            # save list for validation later
            $revList[$rev][$revListNum[$rev]++] = $sub;
        }
    }
    if ($num != $count)         # sanity check
    {
        LogDie("matches do not add up for reviewer $rev");
    }

    $denom    = ($num ? $num : 1);
    $ave     /= $denom;
    $aveRank /= $denom;
    $aveRank  = int($aveRank + 0.5);
    $ave      = sprintf("%5.2f",$ave); 
    print REPORT "\tave:\t$aveRank\t$ave\n";

    $totNum += $num;
    $minNum = ($minNum < $num) ? $minNum : $num;
    $maxNum = ($maxNum > $num) ? $maxNum : $num;
    $rHisto[$num]++;
}

$overallA /= $totNum;
$overallA  = sprintf("%.2f",$overallA); 
$aveNum = $totNum / $maxRev;
$aveNum = sprintf("%.2f",$aveNum); 

if (!$bigReport)
{
    $fname = $tmpFilePrefix."report.txt";
    open REPORT, ">$fname" or LogDie("cannot open $fname");
    print REPORT "Started $startDate\n";
}

print REPORT "========\n";

print REPORT "histogram of number of assignments for submissions:\n";
for ($i = 0; $i <= $maxAssignPerSub; $i++)
{
    print REPORT "\t$i\t$sHisto[$i]\n";
}
print REPORT "========\n";

print REPORT "histogram of number of assignments for reviewers:\n";
for ($i = $minNum; $i <= $maxNum; $i++)
{
    print REPORT "\t$i\t$rHisto[$i]\n";
}
print REPORT "========\n";
print REPORT "Reviewer assignments:\n";
print REPORT "min $minNum max $maxNum mean $aveNum total $totNum assigned to $maxRev reviewers (mean score $overallA)\n";
print REPORT "========\n";
print REPORT "histogram of ranks for submissions:\n";
for ($i = 1; $i <= $maxRev; $i++)
{
    $num = $subRankHisto[$i];
    if ($num)
    {
	print REPORT "\t$i\t$num\n";
    }
}
print REPORT "========\n";
print REPORT "histogram of ranks for reviewers:\n";
for ($i = 1; $i <= $maxSub; $i++)
{
    $num = $revRankHisto[$i];
    if ($num)
    {
	print REPORT "\t$i"."0\t$num\n";
    }
}
print REPORT "========\n";
print REPORT "histogram of scores:\n";
for ($i = 1; $i <= $maxScoreHisto; $i++)
{
    $num = $scoreHisto[$i];
    if ($num)
    {
	$score = $i / 10.0;
	print REPORT "\t$score\t$num\n";
    }
}

$date = `date`;
print REPORT "\nCompleted $date\n";
close(REPORT);

######################################################################
# SECTION: Validate the results by checking for an unstable pair
######################################################################

#
# look for an "unstable pair" as follows.
# consider every pair of reviewer and submission.
# if they are not matched, see if they BOTH would 
# prefer this match to any of their current assignments.
# (note: such a pair should not exist!)
#

print "validating...\n" if ($progress);

for ($rev = 1; $rev <= $maxRev; $rev++)
{
    for ($sub = 1; $sub <= $maxSub; $sub++)
    {
	if ($matched[$rev][$sub] != 1)
	{
	    $score = $scores[$rev][$sub];

	    # look for a worse score on rev's list
	    $worseSub = -1;
	    $num = $revListNum[$rev];
	    for ($i = 0; $i < $num; $i++)
	    {
		$osub   = $revList[$rev][$i];
		$oscore = $scores[$rev][$osub];
		if ($oscore < $score)
		{
		    $worseSub      = $osub;
		    $worseSubScore = $oscore;
		}
	    }

	    # look for a worse score on sub's list
	    $worseRev = -1;
	    $num = $subListNum[$sub];
	    for ($i = 0; $i < $num; $i++)
	    {
		$orev   = $subList[$sub][$i];
		$oscore = $scores[$orev][$sub];
		if ($oscore < $score)
		{
		    $worseRev      = $orev;
		    $worseRevScore = $oscore;
		}
	    }
	    if ($worseSub != -1 && $worseRev != -1)
	    {
		print "validate failed for unstable pair of rev $rev and sub $sub (score $score)\n";
		print "\tmatch with worse sub $worseSub had score $worseSubScore\n";
		print "\tmatch with worse rev $worseRev had score $worseRevScore\n";
		print "\tfor rev $rev and sub $sub score is $scores[$rev][$sub] and matched $matched[$rev][$sub]\n";
		print "\tfor rev $rev and worse sub $worseSub score is $scores[$rev][$worseSub] and matched $matched[$rev][$worseSub]\n";
		print "\tfor worse rev $worseRev and sub $sub score is $scores[$worseRev][$sub] and matched $matched[$worseRev][$sub]\n";
		LogDie("validate failed");
	    }
	}
    }
}

print "done.\n" if ($progress);
$endDate = `date`;
print LOG "finished $endDate";
close(LOG);

######################################################################
# SECTION: Utility functions
######################################################################

# write some text to both the terminal and the log file, and then die
sub LogDie()
{
    my $msg = shift;
    $msg .= "\n";
    print $msg;
    print "quitting\n";
    $endDate = `date`;
    print LOG $msg;
    print LOG "died $endDate";
    close(LOG);
    exit(-1);
}

# write some text to both the terminal and the log file, and then die
sub LogWarn()
{
    my $msg = shift;
    $msg .= "\n";
    print $msg;
    print LOG $msg;
}

######################################################################
# SECTION: Score function says how well review and submission match
######################################################################

# Compute raw score for assigning a submission to a reviewer.
# Takes two arguments: $sub, $rev as well as a bunch of globals noted below.
# See comment at the top of the program for a few general comments on scores.

sub ScoreSubRev()
{
    my $sub = shift;
    my $rev = shift;
    my $score = 0.0;

    # uses these global variables:
    # $subTopicCount[$sub]        - number of topics attached to submission $sub
    # $subTopics[$sub][$w]        - array of "
    # $subTopicWeight[$sub][$top] - weights for "
    # $subNormal[$sub]            - sum of weights for " across all topics
    # $revTopicWeight[$rev][$top] - weight reviewer assigned to topic (or 0 if not)
    # $revNormal[$rev]            - sum of weights for " across all topics

    # loop over keywords for this submission, looking for matches 
    $numWords = $subTopicCount[$sub];
    for ($w = 0; $w < $numWords; $w++)
    {
	$top        = $subTopics[$sub][$w];
	$subWeight  = $subTopicWeight[$sub][$top];
	$revWeight  = $revTopicWeight[$rev][$top];
	$sNormalize =      $subNormal[$sub];
	$rNormalize = sqrt($revNormal[$rev]); # sqrt: penalize less for longer lists

	if ($revWeight > 0.0)	# reviewer also picked this topic
	{
	    $score += $revWeight * $subWeight / ($sNormalize * $rNormalize);

	    # write some notes to the log file (if it exists)
	    print LOG 
		"sub $sub (word $w) rev $rev agree on $top ".
		"(score is now $score)\n";
	}
    }
    return $score;
}
